package com.ztom.v2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ZhangTao
 */
public class Code09FindAllAnagramsInAString {

    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();
        if (m < n) {
            return new ArrayList<>();
        }

        int[] sCount = new int[26];
        int[] pCount = new int[26];
        List<Integer> res = new ArrayList<>();

        int l = 0;
        for (int r = 0; r < m; r++) {
            // 窗口形成过程中, 统计 p 中字符频次
            if (r < n) {
                sCount[s.charAt(r) - 'a']++;
                pCount[p.charAt(r) - 'a']++;
                // 窗口形成
                if (r == n - 1) {
                    if (Arrays.equals(sCount, pCount)) {
                        res.add(0);
                    }
                }
                continue;
            }

            // 窗口滑动
            sCount[s.charAt(l++) - 'a']--;
            sCount[s.charAt(r) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                res.add(l);
            }
        }
        return res;
    }
}
